package simpleGeom;


import java.awt.geom.Line2D;

import java.util.Collections;
import java.util.List;
import java.util.Vector;

import processing.core.PGraphics;
import processing.core.PVector;
import simpleGeom.Vec2D;

public class Triangulator {
	public Vector<HasPos2D> points;
	public Vector<HasPos2D[]> triangles;
	public Object[] inputPts;
	public Vector<Object[]> edges = new Vector<Object[]>();
	Vector<HasPos2D> calcPts = new Vector<HasPos2D>();
	boolean succes = true;
	public Vector<HasPos2D> calcPtsBackup = new Vector<HasPos2D>();
	public Vector<HasPos2D> rest = new Vector<HasPos2D>();

	// public Vector<HasPos2D[]> triangles;
	// Vector<Point2D> linePoints = new Vector<Point2D>();
	public Triangulator() {

	}

	public Triangulator(List<? extends HasPos2D> cpoints) {

		this.points = new Vector<HasPos2D>();
		for (int i = 0; i < cpoints.size(); i++) {
			HasPos2D cP = cpoints.get(i);
			HasPos2D cPN = cpoints.get((i + 1) % cpoints.size());
			// if (Vector2D.dist(cP.getX(), cP.getY(), cPN.getX(),
			// cPN.getY())>0.0001f){
			this.points.add(cP);
			// this.points.add(new Pos2D(cP.getX(), cP.getY()));
			// }
			/*
			 * Pos2D dP=new Pos2D(cP.getX(),cP.getY()); dP.setId(i);
			 * this.points.add(dP);
			 */

		}
		inputPts = new HasPos2D[points.size()];
		for (int i = 0; i < points.size(); i++) {
			HasPos2D cP = points.get(i);
			
			inputPts[i] = cP;
		}

		// triangles = new Vector<HasPos2D[]>();
		calcPts = new Vector<HasPos2D>(points);

		triangles = new Vector<HasPos2D[]>();
		edges = new Vector<Object[]>();
	}

	/*
	 * public Triangulator(List<? extends HasPos2D> cpoints) { inputPts = new
	 * HasPos2D[cpoints.size()];
	 * 
	 * this.points = new Vector<HasPos2D>(); for (int i = 0; i < cpoints.size();
	 * i++) { HasPos2D cP = cpoints.get(i); cP.setId(i); this.points.add(cP);
	 * inputPts[i] = cP; } calcPts = new Vector<HasPos2D>(points);
	 * 
	 * triangles = new Vector<HasPos2D[]>(); edges = new Vector<Object[]>(); }
	 */

	public Triangulator(HasPos2D[] cpoints) {
		this.points = new Vector<HasPos2D>();
		inputPts = new HasPos2D[cpoints.length];
		for (int i = 0; i < cpoints.length; i++) {
			HasPos2D cP = cpoints[i];
			inputPts[i] = cP;
			this.points.add(cP);
		}

		triangles = new Vector<HasPos2D[]>();
		calcPts = new Vector<HasPos2D>(points);
		triangles = new Vector<HasPos2D[]>();
		edges = new Vector<Object[]>();
	}

	public void clipEar() {
		double cArea = getArea(calcPts);

		
		  if (cArea < 0) { Collections.reverse(calcPts); cArea = -cArea; }
		 

		// System.out.println(cArea);
		int i2 = 0;
		int i1 = 0;

		calcPtsBackup = calcPts;
		for (int i0 = 0; i0 < calcPts.size(); i0++) {
			HasPos2D p0 = calcPts.get(i0);
			i1 = (i0 + 1) % calcPts.size();
			HasPos2D p1 = calcPts.get(i1);
			i2 = (i1 + 1) % calcPts.size();
			HasPos2D p2 = calcPts.get(i2);

			if (Line2D.relativeCCW(p0.getX(), p0.getY(), p1.getX(), p1.getY(),
					p2.getX(), p2.getY()) <= 0) {
				//double triArea = getArea(p0, p1, p2);
				// System.out.println("triArea: "+triArea);
				// System.out.println("cArea: "+cArea);
				// if (triArea <= cArea) {
				

				if (!intersectWithLines(p0, p2, calcPts)) {

					Vector<HasPos2D> newPoints = new Vector<HasPos2D>();
					for (int j = 0; j < calcPts.size(); j++) {
						if (j != i1) {
							newPoints.add(calcPts.get(j));
						}
					}
					HasPos2D[] triangle = new HasPos2D[3];
					triangle[0] = p0;
					triangle[1] = p1;
					triangle[2] = p2;
					if (!contains(newPoints, triangle)) {
						// if (Math.abs(getArea(newPoints)) < Math.abs(cArea)) {
						Object[] newEdge = new Object[2];
						newEdge[0] = p0;
						newEdge[1] = p2;// ?
						edges.add(newEdge);

						triangles.add(triangle);
						calcPts = newPoints;
						return;
						// }
					}
					// return newPoints;
					// }
				}

			}

		}
		System.out.println("cArea: " + cArea);
		System.out.println("calcPts.size(): " + calcPts.size());
		calcPts = null;
		
	}

	public void triangulate() {
		
		while (calcPts != null && calcPts.size() > 3) {

			clipEar();
		}
		if (calcPts != null) {
			HasPos2D[] triangle = new HasPos2D[3];
			for (int i = 0; i < 3; i++) {
				triangle[i] = calcPts.get(i);
				triangles.add(triangle);
			}

		} else {
			succes = false;
			System.out.println("triangulation failed");
		}
	}

	public static boolean contains(List<? extends HasPos2D> points,
			HasPos2D[] pts) {
		for (int i = 0; i < points.size(); i++) {
			boolean c = contains(points.get(i), pts);
			if (c)
				return true;
		}
		return false;
	}

	public static boolean contains(HasPos2D cP, HasPos2D[] pts) {
		float x = cP.getX();
		float y = cP.getY();
		int intersections = 0;
		for (int i = 0; i < pts.length; i++) {
			HasPos2D p1 = pts[i];
			if (cP.getX() == p1.getX() && cP.getY() == p1.getY())
				return false;
			HasPos2D p2 = pts[(i + 1) % pts.length];
			if (p1.getX() > p2.getX()) {
				HasPos2D temp = p2;
				p2 = p1;
				p1 = temp;
			}
			if (x >= p1.getX() && x < p2.getX()) {
				if (y < p1.getY() && y < p2.getY()) {
					intersections++;
				} else if (y < p1.getY() || y < p2.getY()) {
					float dX = p2.getX() - p1.getX();
					float dY = p2.getY() - p1.getY();
					float cDX = x - p1.getX();
					float cY = (cDX / dX) * dY + p1.getY();
					if (cY > y) {
						intersections++;
					}
				}
			}

		}
		if (intersections % 2 == 1)
			return true;
		return false;

	}

	public static boolean contains(float x, float y,
			Vector<? extends HasPos2D> pts) {
		int intersections = 0;
		for (int i = 0; i < pts.size(); i++) {
			HasPos2D p1 = pts.get(i);
			HasPos2D p2 = pts.get((i + 1) % pts.size());
			if (p1.getX() > p2.getX()) {
				HasPos2D temp = p2;
				p2 = p1;
				p1 = temp;
			}
			if (x >= p1.getX() && x < p2.getX()) {
				if (y < p1.getY() && y < p2.getY()) {
					intersections++;
				} else if (y < p1.getY() || y < p2.getY()) {
					float dX = p2.getX() - p1.getX();
					float dY = p2.getY() - p1.getY();
					float cDX = x - p1.getX();
					float cY = (cDX / dX) * dY + p1.getY();
					if (cY > y) {
						intersections++;
					}
				}
			}

		}
		if (intersections % 2 == 1)
			return true;
		return false;

	}

	public boolean intersectWithLines(HasPos2D p1, HasPos2D p2,
			Vector<HasPos2D> points) {
		double a1X = p1.getX();
		double a1Y = p1.getY();
		double a2X = p2.getX();
		double a2Y = p2.getY();

		for (int i = 0; i < points.size(); i++) {
			HasPos2D b1 = points.get(i);
			HasPos2D b2 = points.get((i + 1) % points.size());
			if (b1 != p1 && b1 != p2 && b2 != p1 && b2 != p2) {
				double b1X = b1.getX();
				double b1Y = b1.getY();
				double b2X = b2.getX();
				double b2Y = b2.getY();
				if (Line2D.linesIntersect(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X,
						b2Y))
					return true;

			}
			if (b1 != p1 && b1 != p2) {
				// double minX=Math.min(a1, arg1);
				double dSqr = Vec2D.distSqr(a1X, a1Y, a2Y, a2Y);
				double dB1 = Vec2D.distSqr(a1X, a1Y, b1.getX(),
						b1.getY());
				double dB2 = Vec2D.distSqr(a2X, a2Y, b1.getX(),
						b1.getY());

				if (dB1 < dSqr && dB2 < dSqr) {
					if (Line2D.ptSegDist(a1X, a1Y, a2X, a2Y, b1.getX(),
							b1.getY()) < 0.0000001f)
						return true;
				}
			}
		}
		return false;
	}

	public static double getArea(Vector<HasPos2D> points) {
		double area = 0;
		int j;
		for (int i = 0; i < points.size(); i++) {
			j = i + 1;
			if (j == points.size())
				j = 0;
			HasPos2D p1 = points.get(i);
			HasPos2D p2 = points.get(j);
			area += (p1.getX() + p2.getX()) * (p2.getY() - p1.getY());

		}
		return area / 2.;
	}

	public static double getArea(HasPos2D p0, HasPos2D p1, HasPos2D p2) {
		double dX1 = p1.getX() - p0.getX();
		double dY1 = p1.getY() - p0.getY();
		double dX2 = p2.getX() - p0.getX();
		double dY2 = p2.getY() - p0.getY();
		return (dX1 * dY2 - dX2 * dY1) * 0.5;

		// p1.getX()*p0.getY()+p2.getX()*p0.getY()+p0.getX()*
	}

	public void displayTriangles(PGraphics pg) {
		pg.beginShape(PGraphics.TRIANGLES);
		for (int i = 0; i < triangles.size(); i++) {
			HasPos2D[] tri = triangles.get(i);
			for (int j = 0; j < tri.length; j++) {
				HasPos2D pt = tri[j];
				pg.vertex(pt.getX(), pt.getY());

			}
		}
		pg.endShape();
	}

	public Vector<HasPos2D[]> getTriangles() {
		return triangles;
	}
}
